package com.InterestingExercises;

import java.util.Arrays;
import java.util.StringJoiner;

public class BinarySearch二分查找 {
    public static void main(String[] args) {
        /*
        二分查找(折半查找)
        前提:数组/集合中的数据已经是有序的
         */

        int[] arr = new int[]{7, 23, 79, 81, 103, 127, 131, 147};//一个已经有序的数组
        //测试binarySearch
        System.out.println("二分查找结果为:");
        StringJoiner stringJoiner = new StringJoiner(",", "[", "]");
        for (int i = 0; i < arr.length; i++) {
            stringJoiner.add(String.valueOf(binarySearch(arr, arr[i])));
        }
        System.out.println(stringJoiner);

        System.out.print(binarySearch(arr, 104) + " ");
        System.out.print(binarySearch(arr, 5) + " ");
        System.out.println(binarySearch(arr, 150));


        //Arrays类中有多个重载的binarySearch静态函数
        System.out.println(Arrays.binarySearch(arr, 103));
        System.out.println(binarySearch(arr, 103));

    }

    public static int binarySearch(int[] arr, int target) {
        int index = -1;
        int left = 0, right = arr.length - 1, middle = (left + right) / 2;
        while (left <= right) {
            if (arr[middle] == target) {
                return middle;//返回找到的下标
            } else if (target < arr[middle]) {
                right = middle - 1;
            } else {//target > arr[middle]
                left = middle + 1;
            }
            middle = (left + right) / 2;
        }
        return index;//没找到就直接返回-1
    }


}
